package fr.ups.jim.rdf.tp1;

import java.util.Iterator;
import java.util.Map;
import java.util.HashMap;
import java.util.List;
import java.util.ArrayList;
import java.util.Set;
import java.util.HashSet;
import java.lang.Math;
import java.io.InputStream;
import java.io.FileInputStream;
import java.io.InputStreamReader;
import java.io.BufferedReader;
import java.io.FileNotFoundException;
import java.io.IOException;

public class ID3 {

	// For Question 6.1: Return a set of possible values for a given attribute
	private static Set<String> possibleValues(List<Map<String, String>> corpus,
			String attribut) {
		Set<String> res = new HashSet<String>();
		for (Map<String, String> example : corpus) {
			String v = example.get(attribut);
			res.add(v);
		}
		return res;
	}

	// For Question 6.2: From corpus, select all examples whose certain
	// attribute equals to the given value
	private static ArrayList<Map<String, String>> selectSample(
			List<Map<String, String>> corpus, String attribut, String value) {
		ArrayList<Map<String, String>> res = new ArrayList<Map<String, String>>();
		for (Map<String, String> example : corpus) {
			if (example.get(attribut).equals(value)) {
				res.add(example);
			}
		}
		return res;
	}

	// choose the attribute which has the biggest Gain of Information
	private static String chooseAttribute(
			ArrayList<Map<String, String>> examples, List<String> attributes,
			String targetAttribute) throws IOException, FileNotFoundException {

		HashMap<Double, String> gains = new HashMap<Double, String>();
		for (String attribute : attributes) {
			double g = calculateGain(examples, targetAttribute, attribute);
			gains.put(g, attribute);
		}

		double maxValue = max(gains.keySet());
		return gains.get(maxValue);
	}

	private static double max(Set<Double> c) {
		double m = 0.0;
		for (double cc : c) {
			if (m < cc) {
				m = cc;
			}
		}
		return m;
	}

	// Calculate Gain of Information for a given attribute
	private static double calculateGain(
			ArrayList<Map<String, String>> examples, String targetAttribute,
			String attribute) throws IOException, FileNotFoundException {

		double gain_info;
		double entropy_s = ID3.entropy(examples, targetAttribute);

		// get the total number of examples
		int num_example = examples.size();

		// get the total number of all possible values for the given attribute
		Set<String> possible_values = ID3.possibleValues(examples, attribute);
		int num_values = possible_values.size();

		// get frequences for every attribute values
		double[] freq = new double[num_values];
		double[] entropy = new double[num_values];
		String curr_attr_value;
		Iterator<String> itr = possible_values.iterator();
		ArrayList<Map<String, String>> curr_list;
		for (int i = 0; itr.hasNext(); i++) {
			curr_attr_value = itr.next();
			curr_list = ID3.selectSample(examples, attribute, curr_attr_value);
			entropy[i] = ID3.entropy(curr_list, targetAttribute);
			freq[i] = (double) curr_list.size() / num_example;
		}

		for (int i = 0; i < num_values; i++) {
			entropy_s -= freq[i] * entropy[i];
		}

		gain_info = entropy_s;
		return gain_info;
	}

	// Calculate entropy of a data source for a given attribute
	// Calculate the entropy for a specific attribute
	public static double entropy(List<Map<String, String>> examples,
			String attribute) throws IOException, FileNotFoundException {

		// get the total number of examples
		int num_example = examples.size();

		// get the total number of all possible values for the given attribute
		Set<String> possible_values = ID3.possibleValues(examples, attribute);
		int num_values = possible_values.size();

		// get all frequences for each possible attribute values
		// store these frequences in an array
		double[] freq = new double[num_values];

		String attr_value;
		Iterator<String> itr = possible_values.iterator();
		ArrayList<Map<String, String>> curr_list;
		for (int i = 0; itr.hasNext(); i++) {
			attr_value = itr.next();
			curr_list = ID3.selectSample(examples, attribute, attr_value);
			freq[i] = (double) curr_list.size() / num_example;
		}

		// calculate the entropy based on the frequences array
		double entropy = 0.0;
		for (double freq_curr : freq) {
			entropy -= (freq_curr * (Math.log(freq_curr) / Math.log((double) 2)));
		}

		return entropy;
	}

	// la methode pour question 2 : prend en entree le nom du fichier contenant
	// un corpus et
	// retourne une liste de hashmap representant les exemples contenus dans ce
	// fichier
	public static ArrayList<Map<String, String>> readData(String fileName)
			throws IOException, FileNotFoundException {
		ArrayList<Map<String, String>> res = new ArrayList<Map<String, String>>();

		InputStream ips = new FileInputStream(fileName);
		InputStreamReader ipsr = new InputStreamReader(ips);
		BufferedReader br = new BufferedReader(ipsr);
		String line;
		String[] labels = new String[0];
		while ((line = br.readLine()) != null) {
			line = line.trim();
			if (line.startsWith("#")) {
				line = line.substring(1);
				line = line.trim();
				labels = line.split(" ");
				continue;
			}

			Map<String, String> ex = new HashMap<String, String>();
			String[] values = line.split(" ");
			for (int i = 0; i < values.length; i++) {
				ex.put(labels[i], values[i]);
			}
			res.add(ex);
		}

		br.close();

		return res;
	}

	private static String mostFrequent(List<String> lst) {
		HashMap<String, Integer> counts = new HashMap<String, Integer>();
		for (String l : lst) {
			if (!counts.containsKey(l)) {
				counts.put(l, 0);
			}
			counts.put(l, counts.get(l) + 1);
		}

		int maxCount = 0;
		String argmax = null;
		for (Map.Entry<String, Integer> items : counts.entrySet()) {
			if (items.getValue() > maxCount) {
				maxCount = items.getValue();
				argmax = items.getKey();
			}
		}

		return argmax;
	}

	// decide whether all given examples have an identical label
	private static boolean hasSameLabel(
			ArrayList<Map<String, String>> examples, String targetAttribute) {
		boolean hasSameLabel = true;

		// choice of criteria example is abitrary
		// here we choose the first element in the given examples
		Map<String, String> criteria_example = examples.get(0);

		for (Map<String, String> curr_example : examples) {
			if (!curr_example.get(targetAttribute).equals(
					criteria_example.get(targetAttribute))) {
				hasSameLabel = false;
			}
		}

		return hasSameLabel;
	}

	// Use the ID3 algorithm to construct a decision tree for a given dataset (a
	// list of examples)
	public static DecisionNode id3(ArrayList<Map<String, String>> examples,
			String targetAttribute, ArrayList<String> attributes)
			throws IOException {

		DecisionNode root;

		if (attributes.isEmpty() || hasSameLabel(examples, targetAttribute))
			root = new DecisionNode(examples.get(0).get(targetAttribute));
		else {
			String A = chooseAttribute(examples, attributes, targetAttribute);
			ArrayList<Map<String, String>> sub_example;
			Set<String> values = possibleValues(examples, A);
			HashMap<String, DecisionNode> children = new HashMap<String, DecisionNode>();

			for (String attr_val : values) {
				sub_example = selectSample(examples, A, attr_val);

				if (sub_example.isEmpty()) {
					root = new DecisionNode(examples.get(0)
							.get(targetAttribute));
				} else {
					ArrayList<String> attributes_curr = attributes;
					attributes_curr.remove(A);
					children.put(attr_val, ID3.id3(sub_example,
							targetAttribute, attributes_curr));
				}
			}

			root = new DecisionNode(A, children);
		}

		return root;
	}

	// For Question 8, this method calculate the total errors evaluated by the
	// cost function : 0/1
	public static int calculateError(DecisionNode decision_tree, String fileName)
			throws IOException {
		int total_error = 0;

		ArrayList<Map<String, String>> examples = ID3.readData(fileName);
		DecisionNode next;
		// check every independant example
		for (Map<String, String> example : examples) {
			String real_result = example.get("playtennis");
			String predicted_result = "";

			next = decision_tree;

			// based on the given decision_tree (here, generated by ID3)
			// and search the corresponding predicted value until "next" is a
			// leaf
			while (!next.isFinal()) {
				next = next.nextNode(example);
			}
			predicted_result = next.getLabel();

			if (!real_result.equals(predicted_result))
				total_error++;
		}
		return total_error;
	}

	// For Question 11, calculate vocabulary for a given corpus
	// Because we want a set of all different words appeared in the corpus,
	// java.util.Set is an ideal choice.
	public static Set<String> calculateVocabulary(String fileName)
			throws IOException, FileNotFoundException {
		Set<String> vocabulary = new HashSet<String>();

		// establish the input stream for a given file
		InputStream ips = new FileInputStream(fileName);
		InputStreamReader ipsr = new InputStreamReader(ips);
		BufferedReader br = new BufferedReader(ipsr);

		String line; // temproray variable for storing one line text of the
						// given file
		while ((line = br.readLine()) != null) {
			line = line.trim();

			String[] values = line.split(" "); // split one line into a String
												// array
			// values[1] stores the name of the forum, hence ignore the first
			// element
			for (int i = 1; i < values.length; i++) {
				vocabulary.add(values[i]);
			}
		}

		br.close();
		// System.out.println(vocabulary.size());
		return vocabulary;
	}

	// Method 1 for Question 13, we set a limit for the generated decision
	// tree's size
	public static DecisionNode id3LimitSize(
			ArrayList<Map<String, String>> examples, String targetAttribute,
			ArrayList<String> attributes, int tree_size) throws IOException {

		DecisionNode root;

		if (attributes.isEmpty() || hasSameLabel(examples, targetAttribute))
			root = new DecisionNode(examples.get(0).get(targetAttribute));
		else {
			String A = chooseAttribute(examples, attributes, targetAttribute);
			ArrayList<Map<String, String>> sub_example;
			Set<String> values = possibleValues(examples, A);
			HashMap<String, DecisionNode> children = new HashMap<String, DecisionNode>();

			DecisionNode curr;
			for (String attr_val : values) {
				sub_example = selectSample(examples, A, attr_val);

				if (sub_example.isEmpty()) {
					root = new DecisionNode(examples.get(0)
							.get(targetAttribute));
				} else {
					ArrayList<String> attributes_curr = attributes;
					attributes_curr.remove(A);
					// check the size limit here
					if (DecisionNode.NODE_ID <= tree_size)
						children.put(attr_val, ID3.id3LimitSize(sub_example,
								targetAttribute, attributes_curr, tree_size));
					else {
						// if the tree size reaches the limit, return the
						// current decision tree
						root = new DecisionNode(A, children);
						return root;
					}
				}
			}

			root = new DecisionNode(A, children);
		}

		return root;
	}

	// Method 2 for Question 13, construct the ArrayList data for id3LimitSize
	// method
	public static ArrayList<Map<String, String>> readNewsgroup(String fileName)
			throws IOException, FileNotFoundException {

		// firstly, calculate the vocabulary, and construct attributes list
		Set<String> vocabulary = ID3.calculateVocabulary(fileName);
		ArrayList<String> attributes = new ArrayList<String>();
		attributes.add("ForumName");
		for (String attr : vocabulary) {
			attributes.add(attr);
		}

		// Our principle: check whether each word(equivalents to an attribute)
		// appears in current example
		// and set corresponding label value as : "yes" or "no"

		ArrayList<Map<String, String>> res = new ArrayList<Map<String, String>>();

		InputStream ips = new FileInputStream(fileName);
		InputStreamReader ipsr = new InputStreamReader(ips);
		BufferedReader br = new BufferedReader(ipsr);
		String line;
		while ((line = br.readLine()) != null) {
			// get one example from the corpus
			line = line.trim();
			String[] values = line.split(" ");
			// Compared to array, HashSet is more convinient to check the
			// existence of a word
			Set<String> values_set = new HashSet<String>();
			for (String val : values) {
				values_set.add(val);
			}

			Map<String, String> ex = new HashMap<String, String>();
			ex.put(attributes.get(0), values[0]); // insert the forum name
			// check whether this attribute(word) exists in current
			// example(mail)
			for (int i = 1; i < attributes.size(); i++) {
				if (values_set.contains(attributes.get(i)))
					ex.put(attributes.get(i), "yes");
				else
					ex.put(attributes.get(i), "no");
			}

			res.add(ex);
		}

		br.close();

		return res;
	}

	// Method 3 for Question 13, calculate the accumulated error value
	public static int calculateErrorLimitSize(DecisionNode decision_tree,
			String fileName) throws IOException {
		int total_error = 0;

		ArrayList<Map<String, String>> examples = ID3.readNewsgroup(fileName);
		DecisionNode next;

		// check every independant example
		for (Map<String, String> example : examples) {
			try {
				String real_result = example.get("ForumName");
				String predicted_result = "";

				next = decision_tree;

				// based on the given decision_tree (here, generated by ID3)
				// and search the corresponding predicted value until "next" is
				// a leaf
				while (!next.isFinal()) {
					next = next.nextNode(example);

				}
				predicted_result = next.getLabel();

				if (!real_result.equals(predicted_result))
					total_error++;
			} catch (Exception e) {
				total_error++;
			}
		}

		return total_error;
	}

	// For Question 14 : randomly separate the corpus into two parts: corpus for
	// learning, and corpus for test
	// utilise the result generated by "readNewsgroup" as input, that is,
	// corpus.
	public static ArrayList<ArrayList<Map<String, String>>> separateCorpus(
			ArrayList<Map<String, String>> corpus) {

		int random_value;

		// corpus_mix contains only two elements : corpus_app, corpus_test
		ArrayList<ArrayList<Map<String, String>>> corpus_mix = new ArrayList<ArrayList<Map<String, String>>>();
		ArrayList<Map<String, String>> corpus_app = new ArrayList<Map<String, String>>(); // corpus
																							// for
																							// apprentissage
		ArrayList<Map<String, String>> corpus_test = new ArrayList<Map<String, String>>(); // corpus
																							// for
																							// test

		for (Map<String, String> ex : corpus) {
			// generate a random int value between 0 to 100
			random_value = (int) Math.floor((Math.random() * 100));
			if (random_value > 50)
				corpus_app.add(ex);
			else
				corpus_test.add(ex);
		}

		corpus_mix.add(corpus_app);
		corpus_mix.add(corpus_test);

		return corpus_mix;

	}

	// // Methods 2 For question 13, extract possible values for target
	// attributes (specific for newsgroup.dat)
	// public static ArrayList<String> calculateTargetAttrVal(String fileName)
	// throws FileNotFoundException, IOException{
	//    	
	// ArrayList<String> target_values = new ArrayList<String>();
	//    	
	// // establish the input stream for a given file
	// InputStream ips = new FileInputStream(fileName);
	// InputStreamReader ipsr = new InputStreamReader(ips);
	// BufferedReader br = new BufferedReader(ipsr);
	//		
	// String possible_value;
	// String line;
	// while((line=br.readLine())!=null){
	// line = line.trim();
	// // we only need the value before the first whitespace
	// possible_value = line.substring(0, line.indexOf(" "));
	// target_values.add(possible_value);
	// }
	//		
	// return target_values;
	// }

}
